package com.yvon.service.demo.algorithm.offer;

import com.yvon.service.demo.algorithm.offer.ext.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 从上到下打印二叉树
 * 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9832%20-%20I.%20%E4%BB%8E%E4%B8%8A%E5%88%B0%E4%B8%8B%E6%89%93%E5%8D%B0%E4%BA%8C%E5%8F%89%E6%A0%91/README
 */
public class P32_1 {

    public static void main(String[] args) {
        TreeNode nod1 = new TreeNode(1);
        TreeNode nod2 = new TreeNode(2);
        TreeNode nod3 = new TreeNode(2);
        TreeNode nod4 = new TreeNode(3);
        TreeNode nod5 = new TreeNode(4);
        TreeNode nod6 = new TreeNode(4);
        TreeNode nod7 = new TreeNode(3);
        nod1.left = nod2;
        nod1.right = nod3;
        nod2.left = nod4;
        nod2.right = nod5;
        nod3.left = nod6;
        nod3.right = nod7;
        Solution solution = new P32_1().new Solution();
        List<TreeNode> treeNodes = solution.PrintFromTopToBottom(nod1);
        for (int i = 0; i < treeNodes.size(); i++) {
            System.out.print(treeNodes.get(i).value + " ");
        }

        int[] ints = solution.printFromTopToBottom1(nod1);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i] + " ");
        }
    }

    /**
     * https://blog.csdn.net/yue254647202/article/details/78729888
     * 广度优先搜索（BFS）
     *
     */
    class Solution {
        public List<TreeNode> PrintFromTopToBottom(TreeNode root) {
            List<TreeNode> treeList = new ArrayList<>();
            if (root == null) {
                return null;
            }
            treeList.add(root);
            for (int i = 0; i < treeList.size(); i++) {
                TreeNode node = treeList.get(i);
                if (node.left != null) {
                    treeList.add(node.left);
                }
                if (node.right != null) {
                    treeList.add(node.right);
                }
            }
            return treeList;
        }

        /**
         * BFS
         * https://blog.csdn.net/u010414589/article/details/114905914
         *
         * 1.空值处理：如果根节点为空，直接返回空列表
         * 2.初始化：
         *   队列用来按顺序存储节点
         *   集合用来存储节点值
         *
         *           1
         *        |    |
         *        2    3
         *      |  |
         *     4   5
         *
         *    1.首先将根节点加入到队列queue中，因此此时queue中数据为：1                                             queue: (1)；list: ()
         *    2.queue：queue.size = 1，进入循环，节点1出队列queue，节点1的值加入集合list                            queue: ()；list: (1)
         *      因为节点1有左子节点2和右子节点3，因此将左子节点2和右子节点3加入到queue中，此时queue.size = 2；           queue: (2,3)；list: (1)
         *    3.queue.size=2，因此可以进行下一次循环，节点2出队列，节点2的值加入集合list                              queue: (3)；list: (1,2)
         *      因为节点2有左子节点4和右子节点5，因此将左子节点4和右子节点5加入到queue中，此时queue.size=3               queue: (3,4,5)；list: (1,2)
         *    4.queue.size=3，因此可以进行下一次循环，节点3出队列，节点3的值加入集合list                              queue: (4,5)；list: (1,2,3)
         *      节点3无左右节点，结束本次循环，此时queue.size=2
         *    5.queue.size=2，因此可以进行下一次循环，节点4出队列，节点4的值加入集合list                              queue: (5)；list: (1,2,3,4)
         *      节点4无左右节点，结束本次循环，此时queue.size=1
         *    6.queue.size=1，因此可以进行下一次循环，节点5出队列，节点5的值加入集合list                              queue: ()；list: (1,2,3,4,5)
         *      节点4无左右节点，结束本次循环，此时queue.size=0
         *    7.queue.size=0，无法进入循环
         */
        public int[] printFromTopToBottom1(TreeNode root) {
            List<TreeNode> treeList = new ArrayList<>();
            if (root == null) {
                return new int[0];
            }
            Deque<TreeNode> queue = new ArrayDeque<>();
            List<Integer> list = new ArrayList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                // 一次循环处理一层数据
                // size = 等于当前层的节点数量
                int size = queue.size();
                while (size-- > 0) {
                    TreeNode node = queue.poll();
                    list.add(node.value);
                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }
                }
            }
            int i = 0;
            int n = list.size();
            int[] res = new int[n];
            for (Integer e : list) {
                res[i++]= e;
            }
            return res;
        }
    }
}
